package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
 * 235. 二叉搜索树的最近公共祖先
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * <p>
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * <p>
 */
public class LeetCode235 {
    /**
     * 方法一：递归
     * 1. 从根节点开始遍历树
     * 2. 如果节点 p 和节点 q 都在右子树上，那么以右孩子为根节点继续 1 的操作
     * 3. 如果节点 p 和节点 q 都在左子树上，那么以左孩子为根节点继续 1 的操作
     * 4. 如果条件 2 和条件 3 都不成立，这就意味着我们已经找到节 p 和节点 q 的 LCA 了，因为这时p,q分散在左右子树上，或者p或q一个就在根节点上，另一个在子树上，从而该根节点就是LCA
     * <p>
     * 时间复杂度：O(logn) n为树的节点数
     * 空间复杂度：O(logn)
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int val = root.val;
        // 右子树继续遍历
        if (p.val > val && q.val > val) {
            return lowestCommonAncestor(root.right, p, q);
            // 左子树继续遍历
        } else if (p.val < val && q.val < val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        return root;
    }

    /**
     * 方法二：迭代
     * 时间复杂度：O(logn)
     * 空间复杂度：O(1)
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode temp = root;
        while (temp != null) {
            int val = temp.val;
            if (p.val > val && q.val > val) {
                temp = temp.right;
                // 左子树继续遍历
            } else if (p.val < val && q.val < val) {
                temp = temp.left;
            } else {
                return temp;
            }
        }
        return null;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        // [6,2,8,0,4,7,9,null,null,3,5]
        TreeNode root = new TreeNode(6);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(8);
        TreeNode node3 = new TreeNode(0);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(7);
        TreeNode node6 = new TreeNode(9);
        TreeNode node7 = new TreeNode(3);
        TreeNode node8 = new TreeNode(5);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node4.left = node7;
        node4.right = node8;
        LeetCode235 leetCode235 = new LeetCode235();
        System.out.println(leetCode235.lowestCommonAncestor(root, node1, node2).val); // 6
        System.out.println(leetCode235.lowestCommonAncestor(root, node1, node4).val); // 2
        System.out.println(leetCode235.lowestCommonAncestor1(root, node1, node2).val); // 6
        System.out.println(leetCode235.lowestCommonAncestor1(root, node1, node4).val); // 2
    }
}